// LeetCode 主站 Problem Nr. 739: 每日温度

/*
给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。
如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:
	输入: temperatures = [73,74,75,71,69,72,76,73]
	输出: [1,1,4,2,1,1,0,0]
示例 2:
	输入: temperatures = [30,40,50,60]
	输出: [1,1,1,0]
示例 3:
	输入: temperatures = [30,60,90]
	输出: [1,1,0]

提示：
	1 <= temperatures.length <= 105
	30 <= temperatures[i] <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/daily-temperatures
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

func dailyTemperatures(temperatures []int) []int {
    return method3(temperatures)
}

// 暴力解法
func method1(temperatures []int) []int {
    result := make([]int, len(temperatures))

    for i := 0; i < len(temperatures)-1; i++ {
        for j := i+1; j < len(temperatures); j++ {
            if temperatures[i] < temperatures[j] {
                result[i] = j-i
                break
            }
        }
    }

    return result
}

// 基于栈的解法
func method2(temperatures []int) []int {
    result := make([]int, len(temperatures))
    stack := make([]int, 0)
    for i, v := range temperatures {
        for len(stack) > 0 {
            top := stack[len(stack)-1]
            if v > temperatures[top] {
                result[top] = i - top
                stack = stack[:len(stack)-1]
            } else {
                break
            }
        }
        stack = append(stack, i)
    }
    return result
}


func method3(temperatures []int) []int {
    result := make([]int, len(temperatures))
    for i := len(temperatures)-1; i >= 0; i-- {
        j := i+1
        for j < len(temperatures) {
            if temperatures[j] > temperatures[i] {
                result[i] = j-i
                break
            } else if result[j] == 0 {
                break
            } else {
                j += result[j]
            }
        }
    }

    return result
}
